# 回溯算法 全排列2
# 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
def permuteUnique(nums):
    if not nums:
        return []
    used=[0]*len(nums)
    result=[]
    path=[]
    def backtracking(nums,used):
        if len(nums)==len(path):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                if i>0 and not used[i-1] and nums[i]==nums[i-1]:
                    continue
                used[i]=1
                path.append(nums[i])
                backtracking(nums,used)
                used[i]=0
                path.pop()
    backtracking(sorted(nums),used)
    return result
lt=permuteUnique([1,1,2])
print(lt)
